class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1; // 用来放words每个字符串出现个次数
        for (auto& e : words) {
            hash1[e]++;
        }

        int len = words[0].size(); // 每个字符串的长度都是一样的
        int m = words.size();      // 总共有多少个字符串
        

        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash2; // 处理s
            for (int left = i, right = i, count = 0; right + len <= s.size();
                 right += len) {
                // count用来统计有效字符串出现的次数
                string in = s.substr(right, len); // 进入窗口的字符串
                hash2[in]++;
                if (hash2[in] <= hash1[in])
                    count++;

                if (right - left + 1 > len * m) {
                    // 出窗口
                    string out = s.substr(left, len);
                    if (hash2[out] <= hash1[out])
                        count--; // 维护有效字符串个数
                    hash2[out]--;
                    left += len;
                }
                // 更新结果
                if (count == m) {
                    ret.push_back(left);
                }
            }
        }
        return ret;
    }
};
